/* ---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *-------------------------------------------------------------------------------------------- */

import { Iterator, IteratorResult, FIN } from "./iterator";

class Node<E> {
  element: E;
  // eslint-disable-next-line no-use-before-define
  next: Node<E> | undefined;
  // eslint-disable-next-line no-use-before-define
  prev: Node<E> | undefined;

  constructor(element: E) {
    this.element = element;
  }
}

export class LinkedList<E> {
  private _first: Node<E> | undefined;
  private _last: Node<E> | undefined;
  private _size: number = 0;

  get size(): number {
    return this._size;
  }

  isEmpty(): boolean {
    return !this._first;
  }

  clear(): void {
    this._first = undefined;
    this._last = undefined;
    this._size = 0;
  }

  unshift(element: E): () => void {
    return this._insert(element, false);
  }

  push(element: E): () => void {
    return this._insert(element, true);
  }

  private _insert(element: E, atTheEnd: boolean): () => void {
    const newNode = new Node(element);
    if (!this._first) {
      this._first = newNode;
      this._last = newNode;
    } else if (atTheEnd) {
      // push
      const oldLast = this._last!;
      this._last = newNode;
      newNode.prev = oldLast;
      oldLast.next = newNode;
    } else {
      // unshift
      const oldFirst = this._first;
      this._first = newNode;
      newNode.next = oldFirst;
      oldFirst.prev = newNode;
    }
    this._size += 1;
    return this._remove.bind(this, newNode);
  }

  shift(): E | undefined {
    if (!this._first) {
      return undefined;
    } else {
      const res = this._first.element;
      this._remove(this._first);
      return res;
    }
  }

  pop(): E | undefined {
    if (!this._last) {
      return undefined;
    } else {
      const res = this._last.element;
      this._remove(this._last);
      return res;
    }
  }

  private _remove(node: Node<E>): void {
    let candidate: Node<E> | undefined = this._first;
    while (candidate instanceof Node) {
      if (candidate !== node) {
        candidate = candidate.next;
        continue;
      }
      if (candidate.prev && candidate.next) {
        // middle
        const anchor = candidate.prev;
        anchor.next = candidate.next;
        candidate.next.prev = anchor;
      } else if (!candidate.prev && !candidate.next) {
        // only node
        this._first = undefined;
        this._last = undefined;
      } else if (!candidate.next) {
        // last
        this._last = this._last!.prev!;
        this._last.next = undefined;
      } else if (!candidate.prev) {
        // first
        this._first = this._first!.next!;
        this._first.prev = undefined;
      }

      // done
      this._size -= 1;
      break;
    }
  }

  iterator(): Iterator<E> {
    let element: { done: false; value: E };
    let node = this._first;
    return {
      next(): IteratorResult<E> {
        if (!node) {
          return FIN;
        }

        if (!element) {
          element = { done: false, value: node.element };
        } else {
          element.value = node.element;
        }
        node = node.next;
        return element;
      },
    };
  }

  toArray(): E[] {
    const result: E[] = [];
    for (let node = this._first; node instanceof Node; node = node.next) {
      result.push(node.element);
    }
    return result;
  }
}
